/**
 * Let D(n) denote the number of distinct total capacitance values we can
 * obtain using up to n equal-valued capacitors and connect them in parallel
 * or in series. We have: D(1)=1, D(2)=3, D(3)=7 ...
 *
 * Find D(18).
 */

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "euler/fraction.hpp"
#include "euler/static.hpp"
#include "euler.h"

BEGIN_PROBLEM(155, solve_problem_155)
	PROBLEM_TITLE("Counting capacitor circuits")
	PROBLEM_ANSWER("3857447")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(3)
	PROBLEM_TIME_COMPLEXITY("N*(2.62^N)")
	PROBLEM_SPACE_COMPLEXITY("2.62^N")
	PROBLEM_KEYWORDS("combinatorics")
END_PROBLEM()

/*
N(2) = 2, D(2) = 3
N(3) = 4, D(3) = 7
N(4) = 9, D(4) = 15
N(5) = 22, D(5) = 35
N(6) = 53, D(6) = 77
N(7) = 131, D(7) = 179
N(8) = 337, D(8) = 429
N(9) = 869, D(9) = 1039
N(10) = 2213, D(10) = 2525
N(11) = 5691, D(11) = 6235
N(12) = 14517, D(12) = 15463
N(13) = 37017, D(13) = 38513
N(14) = 93731, D(14) = 96231
N(15) = 237465, D(15) = 241519
N(16) = 601093, D(16) = 607339
N(17) = 1519815, D(17) = 1529533
N(18) = 3842575, D(18) = 3857447
D(19) = 9743247
D(20) = 24634043
D(21) = 62335495
D(22) = 157885967
*/

template <class T, class Mapping>
class dense_set
{
	std::vector<bool> table;
	Mapping f;
	size_t count;

public:
	dense_set(size_t capacity)
		: table(capacity), f(), count(0) { }

	dense_set(size_t capacity, Mapping mapping)
		: table(capacity), f(mapping), count(0) { }
	
	bool exists(const T &value) const
	{
		size_t x = f(value);
		return table[x];
	}

	bool insert(const T &value)
	{
		size_t x = f(value);
		if (!table[x])
		{
			table[x] = true;
			++count;
			return true;
		}
		return false;
	}

	size_t size() const { return count; }
};

#define USE_BITSET 1

#if USE_BITSET
// Maps fraction (p,q), p >= q to an index value so that it can be used
// in a dense set.
template <typename T>
struct fraction_mapping
{
	size_t operator () (const euler::fraction<T> &x) const
	{
		size_t p = x.numerator(), q = x.denominator();
		return p*(p-1)/2 + (q-1);
	}
};
#else
template <typename T>
struct fraction_lexico_comparer
{
	bool operator () (const euler::fraction<T> &a, const euler::fraction<T> &b) const
	{
		return a.numerator() < b.numerator() || 
			(a.numerator() == b.numerator() && a.denominator() < b.denominator());
	}
};
#endif

#if 1
// Note: this method can only find the number of resistance values using
// n or fewer resistors (but not exactly n resistors).
static void solve_problem_155()
{
#if 0
	const int N = 5;
	int verbose = 2;
#else
	const int N = 18;
	int verbose = 0;
#endif
	
	typedef euler::fraction<unsigned short> value_t;

	// Let added[n] contain resistance values in B[n] but not in any B[k < n].
	// Let removed[n] contain resistance values in some B[k < n] but not in B[n].
	std::vector<value_t> added[N+1], removed[N+1];

	// Let _all_ be a running union of possible resistance values.
#if USE_BITSET
	const int M = euler::static_fibonacci<N+1>::value;
	dense_set<value_t,fraction_mapping<unsigned short>> all((M+1)*M/2);
#else
	typedef fraction_lexico_comparer<unsigned short> comparer_t;
	std::set<value_t, comparer_t> all;
#endif

	// Add unit resistance value.
	added[1].push_back(1);
	all.insert(1);

	// Only store resistor values that are >= 1.
	for (int n = 2; n <= N; n++)
	{
		std::vector<value_t> current;

		// Split n resistors into two groups of count (k, n - k).
		// For each configuration (k, n - k), connect all possible outcomes 
		// of k resistors and (n - k) resistors.
		// Note that only newly added resistance values need to be checked.
		for (int k = 1; k <= n / 2; k++)
		{
			for (auto it1 = added[k].cbegin(); it1 != added[k].cend(); ++it1)
			{
				for (auto it2 = added[n-k].cbegin(); it2 != added[n-k].cend(); ++it2)
				{
					value_t a = *it1, b = *it2;
#if USE_BITSET
#define APPEND_IF_NOT_EXISTS(x) if (all.insert(x)) current.push_back(x); 

					value_t x;
					x = a + b; 
					APPEND_IF_NOT_EXISTS(x);
					x = a + b.inverse(); 
					APPEND_IF_NOT_EXISTS(x);
					x = a.inverse() + b; 
					APPEND_IF_NOT_EXISTS(x);
					x = a.inverse() + b.inverse();
					if (x.numerator() < x.denominator())
						x = x.inverse();
					APPEND_IF_NOT_EXISTS(x);
#else
					current.push_back(a + b);
					current.push_back(a + b.inverse());
					current.push_back(a.inverse() + b);
					value_t x = a.inverse() + b.inverse();
					if (x.numerator() >= x.denominator())
						current.push_back(x);
					else
						current.push_back(x.inverse());
#endif
				}
			}
		}

#if USE_BITSET
		current.shrink_to_fit();
		added[n].swap(current);
#else
		// Sort the new stuff and remove duplicate elements.
		std::sort(current.begin(), current.end(), comparer_t());
		auto p1 = std::unique(current.begin(), current.end());
		current.resize(p1 - current.begin());

		// Only the newly added resistance values need to be stored.
		added[n].resize(current.size());
		auto ptr = std::set_difference(
			current.cbegin(), current.cend(), 
			all.cbegin(), all.cend(),
			added[n].begin(), comparer_t());
		added[n].resize(ptr - added[n].begin());

		// Update the running union.
		all.insert(added[n].cbegin(), added[n].cend());
#endif

		// Display the resistor values.
		if (verbose >= 2)
		{
			std::cout << "New values for " << n << " resistors:";
			for (auto it = added[n].cbegin(); it != added[n].cend(); ++it)
			{
				std::cout << " " << *it;
			}
			std::cout << std::endl;
		}

		// Display statistics.
		if (verbose)
		{
		//	std::cout << "N(" << n << ") = " << 
		//	(config[n].size()*2-(config[n].front()==1? 1 : 0)) << std::endl;
			std::cout << "D(" << n << ") = " << (all.size()*2-1) << std::endl;
		}
	}

	std::cout << (all.size()*2-1) << std::endl;
}
#else
// This method can be used to find the number of resistance values using
// exact n resistors.
static void solve_problem_155()
{
#if 1
	const int N = 5;
	int verbose = 2;
#else
	const int N = 18;
	int verbose = 0;
#endif
	
	typedef euler::fraction<unsigned short> value_t;

	std::vector<std::vector<value_t>> config(N + 1);
	config[1].push_back(1);
	
	std::set<value_t,fraction_comparer<unsigned short>> all;
	all.insert(config[1].front());

	// Only store resistor values that are >= 1.
	for (int n = 2; n <= N; n++)
	{
		std::set<value_t,fraction_comparer<unsigned short>> current;

		// Split n resistors in two groups of count (k1, k2).
		for (int k1 = 1; k1 <= n / 2; k1++)
		{
			int k2 = n - k1;

			// For each config (k1, k2), connect all possible outcomes of
			// k1 resistors and k2 resistors.
			for (auto it1 = config[k1].cbegin(); it1 != config[k1].cend(); ++it1)
			{
				for (auto it2 = config[k2].cbegin(); it2 != config[k2].cend(); ++it2)
				{
					value_t a = *it1, b = *it2;
					current.insert(a + b);
					current.insert(a + b.inverse());
					current.insert(a.inverse() + b);
					value_t x = a.inverse() + b.inverse();
					if (x.numerator() >= x.denominator())
						current.insert(x);
					else
						current.insert(x.inverse());
				}
			}
		}

		config[n].assign(current.cbegin(), current.cend());
		all.insert(current.cbegin(), current.cend());

		// Display the resistor values.
		if (verbose >= 2)
		{
			std::cout << n << " resistors:";
			for (auto it = config[n].begin(); it != config[n].end(); ++it)
			{
				std::cout << " " << *it;
			}
			std::cout << std::endl;
		}

		// Display statistics.
		if (verbose)
		{
			std::cout << "N(" << n << ") = " << (config[n].size()*2-(config[n].front()==1? 1 : 0))
				<< ", D(" << n << ") = " << (all.size()*2-1) << std::endl;
		}
	}
	std::cout << (all.size()*2-1) << std::endl;
}
#endif
